package Tree116;
import java.util.*;

public class PrintZtree {
    static class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // write code here
        ArrayList<ArrayList<Integer>> p=new ArrayList<ArrayList<Integer>>();
        if(pRoot==null){
            return p;
        }
        Queue<TreeNode> q=new ArrayDeque<>();
        TreeNode cur=pRoot;
        int flag=1;
        q.add(cur);
        while(!q.isEmpty()){
            int n=q.size();
            ArrayList<Integer> m=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode k=q.poll();
                if(flag==1){
                    m.add(k.val);

                }else{
                    m.add(0,k.val);
                }
                if(k.left!=null){
                    q.add(k.left);
                }
                if(k.right!=null){
                    q.add(k.right);
                }
            }
            flag=1-flag;
            p.add(m);
        }

        return p;
    }
}

